//
// Created by yangchao on 2022/6/2.
// 108. 将有序数组转换为二叉搜索树: https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/
//

#include "../DataStructure/TreeNode.h"
#include <vector>
using namespace std;

class SortedArrayToBST {
public:
    //如何选取根节点？高度平衡，则需要每次都选取中间的元素作为根节点
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return helper(nums,0,nums.size()-1);
    }
    TreeNode* helper(vector<int>& nums,int left, int right) {
        if (left > right) return nullptr;
        //总是选择中间位置左边的数字作为根节点
        int mid = (left + right) / 2;
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = helper(nums,left,mid-1);
        root->right = helper(nums,mid+1,right);
        return root ;
    }
};

